#include <queue>
#include <map>
#include <stack>
using namespace std;

#include "triangulation.h"


class ComparePloyVertex {
public:
    bool operator()(ply_vertex* v1, ply_vertex* v2)
    {
		Point2d pos1 = v1->getPos();
		Point2d pos2 = v2->getPos();
		double x1 = pos1.get()[0], x2 = pos2.get()[0];
		double y1 = pos1.get()[1], y2 = pos2.get()[1];
		if(y1 < y2)
			return true;
		else if(y1 == y2)
			return x1 < x2 ? true : false;
		else
			return false;
    }
};


void triangulate_monotone_ploygon(c_polygon& poly, vector<ply_vertex*> sortedVertices, vector<triangle>& triangles){
	  
	  stack<ply_vertex*> stack;
	  stack.push(sortedVertices[0]);
	  stack.push(sortedVertices[1]);
	  for(int i=2;i<poly.getSize();i++)
	  {
		  ply_vertex* current = poly[i];
		  ply_vertex* top = stack.top();
		  double dy1 = (current->getNext()->getPos() - current->getPos()).get()[1];
		  double dy2 = (top->getNext()->getPos() - top->getPos()).get()[1];
		  if(sign(dy1)==sign(dy2)) //same chain
		  {
			  while(stack.size() > 1)
			  {
				  ply_vertex* popped = stack.top();
				  triangle triangle;
				  triangle.v[0] = current->getVID();
				  triangle.v[1] = popped->getVID();
				  triangle.v[2] = popped->getPre()->getVID();
				  stack.pop();
				  triangles.push_back(triangle);
			  }

			  stack.push(poly[i-1]);
			  stack.push(poly[i]);
		  }
		  else //different chains
		  {
			  
		  }
	  }

	  ply_vertex* last = poly[poly.getSize()-1];
	  
	  if(stack.size() > 1)
	  {
		  stack.pop();
		  while(stack.size() > 1)
		  {
			  ply_vertex* popped = stack.top();

			  stack.pop();
		  }
	  }
}

//
//given a polygon, compute a list of triangles that partition the polygon
//
void triangulate(c_polygon& poly, vector<triangle>& triangles )
{
	//TODO: implement this function

	priority_queue<ply_vertex*, vector<ply_vertex*>, ComparePloyVertex> pq;
	vector<ply_vertex*> sortedVertices;
	map<int, int> helper;

	cout<<"Size of poly:"<<poly.getSize()<<endl;
	for(int i=0;i<poly.getSize();i++){
		ply_vertex* vertex = poly[i];
		cout<<"VID:"<<vertex->getVID()<<" Pos:"<<vertex->getPos()<<endl;
		pq.push(vertex);
	}

	while(!pq.empty())
	{
		ply_vertex* vertex = pq.top();
		sortedVertices.push_back(vertex);
		cout<<"VID:"<<vertex->getVID()<<" Pos:"<<vertex->getPos()<<endl;
		pq.pop();

		if(vertex->isStartVertex())
		{
			cout<<"START VERTEX"<<endl;
		}
		else if(vertex->isEndVertex())
		{
			cout<<"End VERTEX"<<endl;
		}
		else if(vertex->isSplitVertex())
		{
			cout<<"SPLIT VERTEX"<<endl;
		}
		else if(vertex->isMergeVertex())
		{
			cout<<"MERGE VERTEX"<<endl;
		}
		else
		{
			cout<<"REGULAR VERTEX"<<endl;
		}
	}

	vector<triangle> tris;
	
	triangulate_monotone_ploygon(poly, sortedVertices, tris);

	triangles.insert(triangles.end(), tris.begin(), tris.end());

	cerr<<"This triangulation method is NOT yet implemented"<<endl;
}
